package sort;

/**
 * @author way
 * @create 2025-03-17 21:10
 */
public class QuickSort {
    int partition1(int[] a, int lo, int hi) {
        int i = lo, j = hi + 1;//左右指针
        int v = a[lo];//切分元素
        while (true) {
            while (a[++i] < v) if (i == hi) break;
            while (a[--j] > v) if (j == lo) break;
            if (i >= j) break;
            swap(a, i, j);
        }
        swap(a, lo, j);//将v放到正确的位置
        return j;
    }

    /**
     * 挖坑法
     *
     * @param a
     * @param lo
     * @param hi
     * @return
     */
    int partition(int[] a, int lo, int hi) {
        int v = a[lo];
        while (lo < hi) {
            while (lo < hi && a[hi] >= v) hi--;
            a[lo] = a[hi];
            while (lo < hi && a[lo] <= v) lo++;
            a[hi] = a[lo];
        }
        a[lo] = v;
        return lo;
    }

    void quickSort(int[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        quickSort(a, lo, j - 1);
        quickSort(a, j + 1, hi);
    }

    public void swap(int[] a, int i, int j) {
        int temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5, 4, 3, 8, 2, 7, 9, 1};
        QuickSort sort = new QuickSort();
        sort.quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}
